1. Field of the Invention
The present invention generally relates to the art of microelectronic integrated circuits, and more specifically to a physical design automation system and method for producing a cell placement for an integrated circuit chip using hierarchical clusterization and placement improvement based on complete replacement of cell clusters.
2. Description of the Related Art
Microelectronic integrated circuits include large numbers of electronic components that are fabricated by layering several different materials on a silicon base or wafer. The design of an integrated circuit transforms a circuit description into a geometric description which is known as a layout. A layout consists of a set of planar geometric shapes in several layers.
The layout is then checked to ensure that it meets all of the design requirements. The result is a set of design files in a particular unambiguous representation known as an intermediate form that describes the layout. The design files are then converted into pattern generator files that are used to produce patterns called masks by an optical or electron beam pattern generator.
During fabrication, these masks are used to pattern a silicon wafer using a sequence of photolithographic steps. The component formation requires very exacting details about geometric patterns and separation between them. The process of converting the specifications of an electrical circuit into a layout is called the physical design. It is an extremely tedious and an error-prone process because of the tight. tolerance requirements and the minuteness of the individual components.
Currently, the minimum geometric feature size of a component is on the order of 0.5 microns. However, it is expected that the feature size can be reduced to 0.1 micron within several years. This small feature size allows fabrication of as many as 4.5 million transistors or 1 million gates of logic on a 25 millimeter by 25 millimeter chip. This trend is expected to continue, with even smaller feature geometries and more circuit elements on an integrated circuit, and of course, larger die (or chip) sizes will allow far greater numbers of circuit elements.
Each microelectronic circuit cell includes a plurality of pins or terminals, each of which is connected to pins of other cells by a respective electrical interconnect wire network or net. A goal of the optimization process is to determine a cell placement and routing such that all of the required interconnects can be made, and the total wirelength and interconnect congestion are minimized.
Existing placement methods based on hierarchical clusterization perform an exhaustive search over all possible configurations. Examples of such method as described in the following articles:
"SIMULTANEOUS FLOOR PLANNING AND GLOBAL ROUTING FOR HIERARCHICAL BUILDING-BLOCK LAYOUT", by W. Dai et al, IEEE Transactions on Computer-Aided Design, Vol. 6, No. 5, 1987, pp. 828-837.
"HIERARCHICAL PLACEMENT AND FLOORPLANNING IN BEAR", by W. Dai et al, IEEE Transactions on Computer-Aided Design, Vol. 8, No. 12, 1989, pp. 1335-1349.
"A NEW CLUSTERING APPROACH AND ITS APPLICATION TO BBL PLACEMENT", by M. Yu et al, IEEE Transactions on Computer-Aided Design, Vol. 9, No. 12, 1990, pp. 665-669.
As a result of the exhaustive search and exponential growth of possible configurations, the number of subclusters in each cluster is very limited (not greater than 4-5). At the same time, this real bound on the number of clusters in each hierarchical level ends up with a reduction of the placement quality.
Investigations in the above referenced article to Yu points out the necessity of using the largest possible groups of clusters and a smaller number of hierarchical levels.
The other disadvantage of known placement algorithms which are based on iterative improvement of an initial placement is the time consuming process of overcoming of the effect of local extrema. Examples of this kind of algorithm are simulated annealing and genetic algorithms which use stochastic principles to overcome the local extrema effect as described in the following articles:
"AN IMPROVED SIMULATED ANNEALING ALGORITHM FOR ROW-BASED PLACEMENT", by C. Sechen et al, IEEE Conference on Computer-Aided Design, 1987, pp. 478-481.
"GENETIC PLACEMENT", by J. Cohoon et al, IEEE International Conference on Computer-Aided Design, 1986, pp. 422-425.
In view of the above, there exists a need in the art for a physical design automation system which is able to generate large clusters without performing an exhaustive search of all possible combinations, while simultaneously overcoming of the effects of local extrema.